/*
* @Author: chenggh
* @Date: 2025-06-13
* @Link to Problem : https://oj.haizeix.com/problem/49
*/

// 思路一：扩展成0-1 背包
// 但是超时，需要进行优化（下一步要做）
#include <iostream>
using namespace std;
int V, N;
int dp[100005] = {0};
int main(){
	cin >> V >> N;
	for(int i = 1, v, w, s; i <= N; i++){
		cin >> v >> w >> s;
		for(int j = 1; j <= s; j++){
			for(int k = V; k >= v; k--){
				dp[k] = max(dp[k], dp[k - v] + w);
			}
		}
	}
	cout << dp[V] << endl;
	return 0;
}